package com.zjsru.studyplan1;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 *
 * 字符串的排列
 *
 * 记 s1的长度为 n，我们可以遍历 s2
 *   中的每个长度为 n 的子串，判断子串和 s1中每个字符的个数是否相等，若相等则说明该子串是 s1的一个排列。
 *
 * 输入：s1 = "ab" s2 = "eidbaooo"
 * 输出：true
 * 解释：s2 包含 s1 的排列之一 ("ba")
 *
 *
 * */
public class checkInclusion {
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();

        if(len1 > len2){
            return false;
        }
        int[] cut1 = new int[26];
        int[] cut2 = new int[26];
        for (int i = 0; i < len1; i++) {
            ++cut1[s1.charAt(i)-'a'];
            ++cut2[s2.charAt(i)-'a'];
        }
        if(Arrays.equals(cut1,cut2)){
            return true;
        }
        for (int i = len1; i < len2; i++) {
            ++cut2[s2.charAt(i)-'a'];
            --cut2[s2.charAt(i-len1)-'a'];
            if(Arrays.equals(cut1,cut2)){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args){
        checkInclusion checkInclusion = new checkInclusion();
        String s1 = "ba";
        String s2 = "eidbaooo";
        System.out.println(checkInclusion.checkInclusion(s1,s2));
    }
}
